Current works on the Approximate Pattern Matching with Wildcards and Length constraints (APMWL) problem can only cope with replacement operation. This paper proposed an Edit Distance Matrix (EDM) method based on dynamic programming and the Approximate Pattern Matching with EDM (APM) algorithm. APM can handle all approximate operations including insertion, replacement and deletion. Moreover, this paper extended APM to the APM-OF algorithm with a strict constraint condition that each character can be used at most once for pattern matching in a sequence. The experiments verify that both APM and APM-OF have significant advantages on matching solutions against other peers. The average improvement rates of matching compared to SAIL-Approx are up to 8.34% and 12.37% respectively. It also demonstrates an advantage on approximate pattern mining that the number of approximate patterns mined by APM-OF is 2.07 times of that mined by OneoffMining.

The cost of a sequence must be calculated and stored in each step by using a classical k-error linear complexity algorithm. If only considering the first drop of its linear complexity namely the minerror linear complexity, a lot of calculation and memory space could be saved. A new algorithm for computing the minerror linear complexity of pn-periodic binary sequences was proposed in this paper. Here p is an odd prime, and 2 is a primitive root (module p2). The new algorithm eliminated the storage and computation of the cost of a sequence, focused on the method of calculation of the linear complexity when k was the minerror which made the first drop of its linear complexity. Besides, theoretical proof was given. Although the new algorithm saved more than half of the storage space and computation time, the results were totally same as the classical algorithm. It is an effective algorithm on the research of sequence's stability.